Contemporary applications and services will run on multiple computing systems that belong to different organizations and fall under different administrative authorities. In order to execute such applications or services that span multiple computing systems, resources within all the computing systems need to be discovered and allocated for these applications. These resources include computing hardware resources, e.g. central processing unit (CPU) resources, storage capacity, e.g. hard drive size, memory size in physical machines and data collectors or data sensors that collect various types of data such as atmospheric or meteorological data and video or audio data. The available resources can be both static and dynamic resources. For example, the memory size or network adaptor speed of a given machine is usually fixed, but the available memory or bandwidth changes frequently over time.
In order to allocate resources among a variety of contemporaneous resource demands, a repository of available resources from various computing systems belonging to all organizations involved needs to be created and maintained. Creation and maintenance of this repository includes discovering resources that are available for allocation. Resource discovery can locate remote resources subject to the specified requirements of a given resource demand and is widely used in many distributed computing systems for a variety of applications. For example, in grid computing, machines or nodes that possess the required CPU and memory resources to run an application are discovered or identified, and then the application is deployed on those identified machines.
A variety of approaches to resource discovery have been proposed. These proposed approaches include the domain name system (DNS) as described in P. Mockapetris & K. J. Dunlap, Development of the Domain Name System, Proceedings of SIGCOMM'88, Stanford, Calif., pp. 123-133 (1988), the lightweight directory access protocol (LDAP/X.500) as described in M. Wahl, T. Howes & S. Kille, RFC 2251-Lightweight Directory Access Protocol (v3), December (1997), ITU-T, Recommendation X.500, January (2001) and D. W. Chadwick, Understanding X.500—The Directory (1996), and the java naming and directory interface (JNDI) as described in Sun Microsystems, Java Naming and Directory Interface—JNDI Documentation, http://java.sun.com/products/jndi/docs.html. All of these systems provide directory service to discover resources and are usually used as the “native” resource discovery service for discovering resources within each organization. However, when multiple organizations, each with its own legacy resource discovery service, want to share their resources across organizational boundaries for applications that need to utilize resources from this shared global pool, a federated resources discovery that can find the required resources regardless of the organizations in which these resources reside, is needed. All of these approaches fail to provide for a federated search. First, these previous attempts at resource discovery were arranged mostly for static resources or resources that change quite slowly, for example host name to internet protocol (IP) mapping. Support for dynamic resources that vary frequently, for example on the scale of tens of minutes or less, using these systems is very limited. More importantly, these systems assume the space or universe of available resources is globally organized into a pre-defined tree hierarchy that is managed in a delegated manner. That is, each organization agrees on such a hierarchy and “owns” a portion, typically a sub-branch or a node, of the tree, and each resource belongs to a certain node in the tree hierarchy.
Due to administrative and trust reasons, autonomous systems may have different perceptions on how resources should be organized. Thus a commonly accepted global organization and management of resources for multiple organizations each having its own preferences or legacy definition of how resources should be organized may not exist. In addition, global organization introduces complexity and restrictions into the allocation of resources. For example, it can be difficult to pre-define the resource hierarchy if new types of resources or new organizations are to be added in the future. Basically, systems that already employ different resource discovery services need to collaborate for common tasks, but it is impossible and inconvenient to change the individual, legacy resource discovery services.
One scalable wide-area resource discovery tool (SWORD) is described by David Oppenheimer, Jeannie Albrecht, David Patterson, and Amin Vahdat in Distributed Resource Discovery on PlanetLab with SWORD, First Workshop on Real, Large Distributed Systems (WORLDS '04), December 2004. This resource discovery service was created for PlanetLab as described by Larry Peterson, Tom Anderson, David Culler, and Timothy Roscoe in A Blueprint for Introducing Disruptive Technology into the Internet, July 2002. The resource discovery tool employed by SWORD utilizes a distributed hash table (DHT) based peer-to-peer network to support multi-dimensional range queries on dynamic resources. One disadvantage of using a peer-to-peer network is that the management of the system is difficult. Peer-to-peer networks are arranged to allow high autonomy of individual nodes, making it quite difficult to facilitate, especially centralized, control and management in the system. In addition, the resource discovery tool in SWORD requires that each individual autonomous system export its complete resource records to the peer-to-peer network, possibly any arbitrary node. This requires that all autonomous systems have high degrees of trust among each other, which can become a problem in reality. Individual autonomous systems may not be willing to expose their original records to an arbitrary node in the outside world.